using System;

namespace Mehroz
{
	/// <summary>
	/// Summary description for MazeSolver.
	/// Class name: MazeSolver
	/// Developed by: Syed Mehroz Alam
	/// Email: smehrozalam@yahoo.com
	/// URL: Programming Home "http://www.geocities.com/smehrozalam/"
	/// 
	/// Constructors:
	/// 	( int[,] ):	takes 2D integer array	
	/// 	( int Rows, int Cols )	initializes the dimensions, indexers may be used 
	/// 							to set individual elements' values
	/// 
	/// Properties:
	/// 	Rows: returns the no. of rows in the current maze
	/// 	Cols: returns the no. of columns in the current maze
	/// 	Maze: returns the current maze as a 2D array
	/// 	PathCharacter: to get/set the value of path tracing character
	/// 	AllowDiagonal: whether diagonal paths are allowed
	/// 
	/// Indexers:
	/// 	[i,j] = used to set/get elements of maze
	/// 
	/// Public Methods (Description is given with respective methods' definitions)
	///		int[,] FindPath(int iFromY, int iFromX, int iToY, int iToX)
	/// 
	/// Private Methods
	///		void GetNodeContents(int[,] iMaze, int iNodeNo)
	///		void ChangeNodeContents(int[,] iMaze, int iNodeNo, int iNewValue)
	///		int[,] Search(int iBeginningNode, int iEndingNode)
	/// 
	/// </summary>
	delegate void MazeChangedHandler(int iChanged, int jChanged);
	class MazeSolver
	{

		/// <summary>
		/// Class attributes/members
		/// </summary>
        /// 
        const int TurnCost=10;

		int[,] m_iMaze;
		int m_iRows;
		int m_iCols;
		int iPath=100;
		bool diagonal=false;
		public event MazeChangedHandler OnMazeChangedEvent;
        

		/// <summary>
		/// Constructor 1: takes a 2D integer array
		/// </summary>
		public MazeSolver(int[,] iMaze)
		{
			m_iMaze=iMaze;
			m_iRows=iMaze.GetLength(0);
			m_iCols=iMaze.GetLength(1);
		}

		/// <summary>
		/// Constructor 2: initializes the dimensions of maze, 
		/// later, indexers may be used to set individual elements' values
		/// </summary>
		public MazeSolver(int iRows, int iCols)
		{
			m_iMaze=new int[iRows, iCols];
			m_iRows=iRows;
			m_iCols=iCols;
		}
			
		/// <summary>
		/// Properites:
		/// </summary>
		public int Rows
		{
			get { return m_iRows; }
		}

		public int Cols
		{
			get { return m_iCols; }
		}
		public int[,] GetMaze
		{
			get { return m_iMaze; }
		}
		public int PathCharacter
		{
			get { return iPath; }
			set
			{
				if (value==0)
					throw new Exception("Invalid path character specified");
				else
					iPath=value;
			}
		}
		public bool AllowDiagonals
		{
			get {	return diagonal;	}
			set {	diagonal=value;		}
		}


		/// <summary>
		/// Indexer
		/// </summary>
		public int this[int iRow, int iCol]
		{
			get { return m_iMaze[iRow,iCol]; }
			set 
			{ 
				m_iMaze[iRow,iCol]=value;
				if (this.OnMazeChangedEvent!=null)	// trigger event
					this.OnMazeChangedEvent(iRow, iCol);
			}
		}

		/// <summary>
		/// The function is used to get the contents of a given node in a given maze,
		///  specified by its node no.
		/// </summary>
		private int GetNodeContents(int[,] iMaze, int iNodeNo)
		{
			int iCols=iMaze.GetLength(1);
			return iMaze[iNodeNo/iCols,iNodeNo-iNodeNo/iCols*iCols];
		}

		/// <summary>
		/// The function is used to change the contents of a given node in a given maze,
		///  specified by its node no.
		/// </summary>
		private void ChangeNodeContents(int[,] iMaze, int iNodeNo, int iNewValue)
		{
			int iCols=iMaze.GetLength(1);
			iMaze[iNodeNo/iCols,iNodeNo-iNodeNo/iCols*iCols]=iNewValue;
		}
		
		/// <summary>
		/// This public function finds the shortest path between two points
		/// in the maze and return the solution as an array with the path traced 
		/// by "iPath" (can be changed using property "PathCharacter")
		/// if no path exists, the function returns null
		/// </summary>
		public int[,] FindPath(int iFromY, int iFromX, int iToY, int iToX)
		{
			int iBeginningNode = iFromY*this.Cols + iFromX;
			int iEndingNode = iToY*this.Cols + iToX;
			return ( Search(iBeginningNode, iEndingNode) ) ;
		}



		/// <summary>
		/// Internal function for that finds the shortest path using a technique
		/// similar to breadth-first search.
		/// It assigns a node no. to each node(2D array element) and applies the algorithm
		/// </summary>
		private enum Status
		{	Ready,	Waiting,	Processed	}
		private int[,] Search(int iStart, int iStop)
		{
			const int empty=0;
		
            int i,j;
			int iRows=m_iRows;
			int iCols=m_iCols;
			int iMax=iRows*iCols;
            int Max = Int32.MaxValue;

            int [] min;

            Heap heap = new Heap(iMax);

			int[,] cost=new int[iMax,4];  // 0 up 1 right 2 down 3 left
			int[,,] Origin=new int[iMax,4,2];
			int iFront=0, iRear=0;

			//check if starting and ending points are valid (open)
			if ( GetNodeContents(m_iMaze, iStart)!=empty || GetNodeContents(m_iMaze, iStop)!=empty )
			{
				return null;
			}
		
			//create dummy array for storing status
			int[,] iMazeStatus=new int[iRows,iCols];
			//initially all nodes are ready
			for(i=0;i<iRows;i++)
				for(j=0;j<iCols;j++)
					iMazeStatus[i,j]=(int)Status.Ready;

            for (i=0;i<iMax;i++)
            {
                for (j = 0; j < 4; j++)
                {
                    cost[i, j] = Max;
                    Origin[i,j,0] = -1;
                    Origin[i, j, 1] = -1;
                }
            }

			//add starting node to Q
            heap.insert(iStart,0);
            cost[iStart,1]=0;
            cost[iStart,0]=TurnCost;
            cost[iStart,2]=TurnCost;
            cost[iStart,3]=TurnCost;
			
            min=heap.getMin();

            int iCurrent,iNext,newCost,newCostDir,tempCost,sign;// iLeft, iRight, iTop, iDown, iRightUp, iRightDown, iLeftUp, iLeftDown;
            int[] offset={-Cols,1,iCols,-1};
			while(min!=null)	// while Q not empty	
			{
				iCurrent=min[0];
                if (iCurrent == iStop) break;
                if ((GetNodeContents(iMazeStatus, iCurrent) == (int)Status.Processed))
                {
                    min = heap.getMin();
                    continue;
                }

                for (i=0;i<4;i++)
                {
                    iNext=iCurrent+offset[i];

                    if ((i==1) || (i==3))
                    {
                        if (iCurrent/iCols!=iNext/iCols) continue;
                    }
                    if ((iNext>=0) && (iNext<iMax) && (GetNodeContents(m_iMaze, iNext)==empty))
                    {
                        if ((GetNodeContents(iMazeStatus, iNext)==(int) Status.Processed))
                            continue;
                        newCost=Max;
                        newCostDir = 0;
                        for (j=0;j<4;j++)
                        {
                            tempCost=cost[iCurrent,j]+1;
                            if (j!=i) tempCost+=TurnCost;
                            if (tempCost<newCost) {
                                newCost=tempCost;
                                newCostDir=j;
                            }
                        }
                        if ((GetNodeContents(iMazeStatus, iNext)==(int) Status.Ready) || 
                            (GetNodeContents(iMazeStatus,iNext)==(int) Status.Waiting))
                        {
                            sign=Max;
                            for (j=0;j<4;j++)
                            {
                                tempCost=newCost;
                                if (j!=i) tempCost+=TurnCost;
                                
                                if (tempCost<cost[iNext,j]) 
                                {
                                    cost[iNext,j]=tempCost;
                                    Origin[iNext,j,0]=iCurrent;
                                    Origin[iNext,j,1]=newCostDir;
                                    if (tempCost<sign) sign=tempCost;
                                }
                            }
                            if (sign < Max)
                            {
                                heap.insert(iNext, sign);
                                ChangeNodeContents(iMazeStatus, iNext, (int)Status.Waiting);
                            }
                        }
                    }
                }
			
				//change status of current node to processed
				ChangeNodeContents(iMazeStatus, iCurrent, (int)Status.Processed);
				min=heap.getMin();			
			}

			//create an array(maze) for solution
			int[,] iMazeSolved=new int[iRows,iCols];
			for(i=0;i<iRows;i++)
				for(j=0;j<iCols;j++)
					iMazeSolved[i,j]=m_iMaze[i,j];

			//make a path in the Solved Maze
            i = iStop; sign = 0; tempCost = Max;
           
            for (j=0;j<4;j++)
                if (cost[i, j] < tempCost)
                {
                    tempCost = cost[i, j];
                    sign = j;
                }
                        
			while ((i != iStart) && (i != -1))
            {
                ChangeNodeContents(iMazeSolved, i, iPath);
                j = Origin[i, sign, 0];
                sign = Origin[i, sign, 1];
                i = j;
            }

			if (i == iStart)
                return (iMazeSolved);
            else return null;
		}
	}

}

class Heap
{
    int length;
    int n;
    int[,] list;

    int main(String[] args)
    {
        Heap h = new Heap(100);
        int[] t;

        h.insert(1, 100);

        h.insert(2, 30);

        h.insert(3, 150);

        h.insert(4, 160);

        h.insert(5, 10);

        h.print();

        t = h.getMin();
        System.Console.WriteLine("min:" + t[0] + "," + t[1]);

        t = h.getMin();
        System.Console.WriteLine("min:" + t[0] + "," + t[1]);

        System.Console.Read();
        return 1;
    }

    public Heap(int l)
    {
        length = l;
        list = new int[length+1,2];
        n = 0;
    }

    public void insert(int num, int value)
    {
        int i,p,j;
        n++;
        list[n, 0] = num;
        list[n, 1] = value;

        i = n; 
        p = i / 2;
        while ((i > 1) && (list[p,1]>list[i,1]))
        {
            j = list[i, 0];
            list[i, 0] = list[p, 0];
            list[p, 0] = j;
            j = list[i, 1];
            list[i, 1] = list[p, 1];
            list[p, 1] = j;

            i = p;
            p = i / 2;
        }
    }

    public int[] getMin()
    {
        int i,l, r, s,j;
        int[] re=new int[2];

        if (n < 1) return null;

        list[0, 0] = list[1, 0];
        list[0, 1] = list[1, 1];

        list[1, 0] = list[n, 0];
        list[1, 1] = list[n, 1];

        n--;
        i = 1;

        while (i < n)
        {
            l = i * 2;
            r = i * 2 + 1;

            if ((l <= n) && (list[l, 1] < list[i, 1]))
                s = l;
            else s = i;
            if ((r <= n) && (list[r, 1] < list[s, 1]))
                s = r;
            if (s != i)
            {
                j = list[i, 0];
                list[i, 0] = list[s, 0];
                list[s, 0] = j;
                j = list[i, 1];
                list[i, 1] = list[s, 1];
                list[s, 1] = j;
                i = s;
            }
            else break;            
        }

        re[0] = list[0, 0];
        re[1] = list[0, 1];       
        return re;
    }

    public void print()
    {
        for (int i = 1; i <= n; i++)
        {

            System.Console.WriteLine( list[i, 0] + "," + list[i, 1] + "  ");
        }
        System.Console.WriteLine(""); 
    }
}